/**
 * @file crossings.c
 * @brief Gives an interactive illustration of either the barycenter or the
 *  median heuristic for bigraph crossing minimization.
 * @author Matt Stallmann
 * @date 2006/06/22
 * $Id: crossings.c 10 2007-06-28 20:08:57Z mfms $
 */

/*
 *  Copyright (C) 2006  Matthias Stallmann
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include<stdio.h>
#include<stdlib.h>
#include<float.h>
#include "Gdr.h"

#define TOP_LEVEL_AXIS 150
#define BOTTOM_LEVEL_AXIS 350

int visited[MAX_VERTEX];        /* non-zero if this vertex has been visited
                                   during the dfs for bipartitioning */
int rank[MAX_VERTEX];           /* order of appearance on the side */
float average[MAX_VERTEX];      /* mean or median, used as a basis for
                                   sorting */

/* declarations and macros for the animation */
#define MSG_SIZE 511            /* maximum length of a message */
char msg[MSG_SIZE];
TWIN pwin;                      /* window for user prompts */
#define XW 1                    /* prompt window coordinates */
#define YW 1
#define init_prompt_window (pwin = create_text_window(XW, YW, ""))
#define destroy_prompt_window (kill_window(pwin))
#define wait(msg) (write_text_window(pwin, msg), suspend_animation(),\
               hide_window(pwin))

/** array representing the "top" bipartition */
vertex top_level[MAX_VERTEX];
/** actual size of top bipartition */
int top_level_size = 0;

/** array representing the "bottom" bipartition */
vertex bottom_level[MAX_VERTEX];
/** actual size of bottom bipartition */
int bottom_level_size = 0;

/** Which level is being permuted */
enum {TOP = 0, BOTTOM = 1} current_permute_level = TOP;
#define other_level(level) (1 - level)

/** Which method is used to compute averages */
enum {BARYCENTER, MEDIAN} averaging_method;

/** Return an allocated string representation of int i.
    Assume i is no more than the maximum vertex number */
char * string_from_int(int i) {
  char *stg;
  stg = (char *) malloc(MAX_VERTEX_STRING_LENGTH + 1);
  sprintf(stg, "%d", i);
  return (stg);
}

/** Return an allocated string representation of float f. */
char * string_from_float(float f) {
  char *stg;
  int float_size = 5;           /* see format specs below */
  stg = (char *) malloc(float_size + 1);
  sprintf(stg, "%5.2f", f);
  return (stg);
}

/** Unhighlight all vertices in other level */
void unhighlight_other_level(void) {
  vertex * level_ptr;
  vertex * level_end_ptr;
  if( current_permute_level == BOTTOM ) {
    level_ptr = top_level;
    level_end_ptr = top_level + top_level_size;
  }
  else {
    level_ptr = bottom_level;
    level_end_ptr = bottom_level + bottom_level_size;
  }
  while( level_ptr < level_end_ptr ) {
    un_highlight_vertex(*level_ptr);
    ++level_ptr;
  }
}

/** Highlight all vertices in current level */
void highlight_current_permute_level(void) {
  vertex * level_ptr;
  vertex * level_end_ptr;
  if( current_permute_level == TOP ) {
    level_ptr = top_level;
    level_end_ptr = top_level + top_level_size;
  }
  else {
    level_ptr = bottom_level;
    level_end_ptr = bottom_level + bottom_level_size;
  }
  while( level_ptr < level_end_ptr ) {
    highlight_vertex(*level_ptr);
    ++level_ptr;
  }
}

/** Compare x-coordinates of two vertices (pointers) */
int compare_x_coordinates(const void * v1_void_ptr,
                          const void * v2_void_ptr) {
  vertex * v1_ptr = (vertex *) v1_void_ptr;
  vertex * v2_ptr = (vertex *) v2_void_ptr;
  return vertex_x(*v1_ptr) - vertex_x(*v2_ptr);
}

/** Sort vertices on other level by x-coordinate */
void sort_other_level(void) {
  if( current_permute_level == BOTTOM ) {
    qsort(top_level, top_level_size,
          sizeof(vertex), compare_x_coordinates);
  }
  else {
    qsort(bottom_level, bottom_level_size,
          sizeof(vertex), compare_x_coordinates);
  }
}

/** Display labels indicating the vertex order on the other level and set up
    rank for each vertex */
void display_sort_results(void) {
  vertex * level_ptr;
  vertex * level_end_ptr;
  int index = 0;
  if( current_permute_level == BOTTOM ) {
    level_ptr = top_level;
    level_end_ptr = top_level + top_level_size;
  }
  else {
    level_ptr = bottom_level;
    level_end_ptr = bottom_level + bottom_level_size;
  }
  while( level_ptr < level_end_ptr ) {
    char * index_string = string_from_int(index);
    rank[*level_ptr] = index;
    change_vertex_label(*level_ptr, index_string);
    expose_vertex_label(*level_ptr);
    free(index_string);
    ++level_ptr;
    ++index;
  }
}

/** Use the designated heuristic to compute averages (each vertex on the
    current level is assigned an average based on its edges to the other
    level) */
void compute_averages(void) {
  vertex * level_ptr;
  vertex * level_end_ptr;
  if( averaging_method != BARYCENTER ) {
    wait("MEDIAN not implemented.\nClick RESUME to continue with BARYCENTER.");
  }
  if( current_permute_level == TOP ) {
    level_ptr = top_level;
    level_end_ptr = top_level + top_level_size;
  }
  else {
    level_ptr = bottom_level;
    level_end_ptr = bottom_level + bottom_level_size;
  }
  while( level_ptr < level_end_ptr ) {
    vertex w;
    edge e;
    float sum = 0;
    int degree = 0;
    for_adjacent(*level_ptr, e, w) {
      sum += rank[w];
      ++degree;
    }
    average[*level_ptr] = sum / degree; 
    ++level_ptr;
  }
}

/** Display averages on current level as vertex labels */
void display_averages(void) {
  vertex * level_ptr;
  vertex * level_end_ptr;
  if( current_permute_level == TOP ) {
    level_ptr = top_level;
    level_end_ptr = top_level + top_level_size;
  }
  else {
    level_ptr = bottom_level;
    level_end_ptr = bottom_level + bottom_level_size;
  }
  while( level_ptr < level_end_ptr ) {
    char * avg_string = string_from_float(average[*level_ptr]);
    change_vertex_label(*level_ptr, avg_string);
    expose_vertex_label(*level_ptr);
    free(avg_string);
    ++level_ptr;
  }
}

/** Put vertices of current level in a straight horizontal line, equally
    spaced */
void align_other_level(void) {
  int horizontal_axis;
  vertex * level_ptr;
  vertex * level_end_ptr;
  int current_x_coordinate;
  int inter_vertex_distance;
  if( current_permute_level == BOTTOM ) {
    horizontal_axis = TOP_LEVEL_AXIS;
    level_ptr = top_level;
    level_end_ptr = top_level + top_level_size;
    inter_vertex_distance = window_width() / (top_level_size + 1);
  }
  else {
    horizontal_axis = BOTTOM_LEVEL_AXIS;
    level_ptr = bottom_level;
    level_end_ptr = bottom_level + bottom_level_size;
    inter_vertex_distance = window_width() / (bottom_level_size + 1);
  }
  current_x_coordinate = 0;
  while( level_ptr < level_end_ptr ) {
    current_x_coordinate += inter_vertex_distance;
    move_vertex_absolute(*level_ptr, current_x_coordinate, horizontal_axis);
    ++level_ptr;
  }
}

/** Permute the current level with help from the user */
void permute_current_permute_level(void) {
  unhighlight_other_level();
  highlight_current_permute_level();
  sort_other_level();
  align_other_level();
  display_sort_results();
  compute_averages();
  display_averages();
  wait("Rearrange highlighted vertices based on averages.\n"
       "Click RESUME to continue.");
} /* end, permute_current_permute_level */

/** partition the bipartite graph into two layers, putting vertex v on the
    current level (recursive dfs)  */
void do_bipartition(vertex v) {
  vertex w;
  edge e;
  if( ! visited[v] ) {
    visited[v] = 1;
    if( current_permute_level == TOP )
      top_level[top_level_size++] = v;
    else bottom_level[bottom_level_size++] = v;

    for_adjacent(v, e, w) {
      current_permute_level = other_level(current_permute_level);
      do_bipartition(w);
      current_permute_level = other_level(current_permute_level);
    }
  }
}

/** Put vertices of each level in a straight horizontal line, equally spaced */
void align_both_levels(void) {
  sort_other_level();
  align_other_level();
  current_permute_level = other_level(current_permute_level);
  sort_other_level();
  align_other_level();
  current_permute_level = other_level(current_permute_level);
}

void animat(void) {
  char answer[ MSG_SIZE ];
  vertex v;
  edge e;
  
  init_prompt_window;
#if 0
  query( 0, 0, "Barycenter or median? (b/m)? ", answer );
  averaging_method = (answer[0] == 'b') ? BARYCENTER : MEDIAN;
#else
  averaging_method = BARYCENTER;
#endif
  for_all_edges(e) {
    hide_edge_label(e);
  }
  for_all_vertices(v) {
    visited[v] = 0;
  }
  do_bipartition(get_a_vertex());
  align_both_levels();
  current_permute_level = TOP;
  do {
    permute_current_permute_level();
    query(0, 0, "Continue (y/n)? ", answer );
    current_permute_level = other_level(current_permute_level);
  } while ( answer[0] == 'y' );

  destroy_prompt_window;
  top_level_size = bottom_level_size = 0;
} /* animat ends */

/*  [Last modified: 2007 06 28 at 19:43:33 GMT] */
